class Solution:
    def __init__(self):
        self.matrixMap: list[list[int]] = []

    # dfs入口
    def dfs(self, beginRoot: int) -> int:
        # 去重
        visited: list[bool] = [False for _ in range(len(self.matrixMap))]
        tempDeep = 0
        res: list[int] = [beginRoot, 0]

        # dfs实现
        def _dfs(root: int, tempDeep: int, res: list[int]) -> None:
            # 访问
            visited[root] = True
            tempDeep += 1

            # 查找下一个
            for i in range(len(self.matrixMap[root])):
                # 节点已访问
                if visited[self.matrixMap[root][i]] is True:
                    continue
                _dfs(self.matrixMap[root][i], tempDeep, res)

            # 回溯
            if tempDeep > res[1]:
                res[1] = tempDeep
                res[0] = root
            tempDeep -= 1

        # dfs出口
        _dfs(beginRoot, tempDeep, res)
        visited.clear()
        return res[0]

    def find_way(self, begin: int, end: int) -> list[int]:
        # 去重
        visited: list[bool] = [False for _ in range(len(self.matrixMap))]
        res: list[int] = []

        # dfs实现
        def _dfs(root: int) -> bool:
            # 访问
            visited[root] = True
            if root == end:
                res.append(root)
                return True

            # 查找下一个
            for i in range(len(self.matrixMap[root])):
                # 节点未连接或节点已访问
                if visited[self.matrixMap[root][i]] is True:
                    continue

                flag = _dfs(self.matrixMap[root][i])
                if flag:
                    res.append(root)
                    return True

            return False

        _dfs(begin)
        res_len = len(res)
        if res_len & 1:
            return [res[res_len >> 1]]
        else:
            return [res[(res_len - 1) >> 1], res[res_len >> 1]]

    def findMinHeightTrees(self, n: int, edges: list[list[int]]) -> list[int]:
        # 树转图
        self.matrixMap = [[] for _ in range(n)]
        for edge in edges:
            self.matrixMap[edge[0]].append(edge[1])
            self.matrixMap[edge[1]].append(edge[0])

        a = self.dfs(0)
        b = self.dfs(a)

        return self.find_way(a, b)
